package com.smh;

/**
 * @author shiminghui
 * @date 2025/2/28 20:02
 * @description: TODO
 */
public class _034_avl树 {


    public static class AVLTree {

        private AVLNode root = null;

        public AVLTree() {
        }

        /**
         * 平衡节点
         *
         * @param node
         * @return
         */
        private AVLNode balance(AVLNode node) {
            if (node == null)
                return null;
            int balanceFactor = getBalanceFactor(node);
            if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) { //LL
                leftRotate(node);
            } else if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { //LR
                leftRightRotate(node);
            } else if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { //RL
                rightLeftRotate(node);
            } else if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) { //RR
                rightRotate(node);
            }
            return node;
        }

        /**
         * 先右旋根节点的右节点，再左旋根节点
         *
         * @param node
         * @return
         */
        private AVLNode rightLeftRotate(AVLNode node) {
            node.right = rightRotate(node.right);
            node = leftRotate(node);
            return node;
        }

        /**
         * 先左旋根节点的左节点，再右旋根节点
         *
         * @param node
         * @return
         */
        private AVLNode leftRightRotate(AVLNode node) {
            node.left = leftRotate(node.left);
            node = rightRotate(node);
            return node;
        }

        /**
         * 左旋转
         *
         * @param node
         * @return 旋转后的根节点
         */
        private AVLNode leftRotate(AVLNode node) {
            AVLNode right = node.right;
            node.right = right.left;
            right.left = node;
            updateHeight(node); // 更新节点高度，顺序很重要，否则会出错
            updateHeight(right);
            return right;
        }

        /**
         * 右旋转
         *
         * @param node
         * @return 旋转后的根节点
         */
        private AVLNode rightRotate(AVLNode node) {
            AVLNode left = node.left;
            node.left = left.right;
            left.right = node;
            updateHeight(node);
            updateHeight(left);
            return left;
        }

        /**
         * 平衡因子
         *
         * @param node
         * @return
         */
        private int getBalanceFactor(AVLNode node) {
            if (node == null) {
                return 0;
            }
            return getHeight(node.left) - getHeight(node.right);
        }

        /**
         * 插入节点
         *
         * @param value
         */
        public void put(int value) {
            root = doPut(value, root);
        }

        /**
         * 递归插入节点
         *
         * @param value
         * @param node
         * @return
         */
        private AVLNode doPut(int value, AVLNode node) {
            if (node == null) {
                return new AVLNode(value);
            }
            if (value < node.value) {
                node.left = doPut(value, node.left);
            } else if (value > node.value) {
                node.right = doPut(value, node.right);
            } else {
                node.value = value;
            }
            updateHeight(node); // 更新节点高度,从下到上，每一层都要更新
            return balance(root); // 插入完节点后，需要重新平衡整个树
        }

        /**
         * 删除节点
         *
         * @param value
         * @return
         */
        public void remove(int value) {

        }

        /**
         * 递归删除节点
         *
         * @param node
         * @param value
         */
        private AVLNode doRemove(AVLNode node, int value) {
            if (node == null) {
                return null;
            }
            if (value < node.value) {
                node.left = doRemove(node.left, value);
            } else if (value > node.value) {
                node.right = doRemove(node.right, value);
            } else {
                // 找到了
                // 当删除节点没有左孩子
                if (node.left == null) {
                    node = node.right;
                }
                // 当删除节点没有右孩子
                else if (node.right == null) {
                    node = node.left;
                }
                // 当删除节点有左右孩子
                else {
                    // 查找当前节点的后继节点
                    AVLNode post = node.right;
                    AVLNode postParent = null;
                    while (post.left != null) {
                        postParent = post;
                        post = post.left;
                    }
                    post.right = doRemove(node.right, post.value);
                    post.left = node.left;
                    node = post;
                }
            }
            // 更新节点高度
            updateHeight(node);
            return balance(node);
        }

        /**
         * 更新节点的高度
         *
         * @param node
         * @return
         */
        private int updateHeight(AVLNode node) {
            return node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        }


        /**
         * 获取节点的高度
         *
         * @param node
         * @return
         */
        private int getHeight(AVLNode node) {
            return node == null ? 0 : node.height;
        }

        private static class AVLNode {
            private AVLNode left;
            private AVLNode right;
            private int height = 1;
            private int value;

            public AVLNode(int value) {
                this.value = value;
            }

            public AVLNode() {
            }

            public AVLNode(AVLNode left, AVLNode right, int value) {
                this.left = left;
                this.right = right;
                this.value = value;
            }
        }

    }

}
